
import java.util.*;
/**
 * 
 * 兑换零钱(一)
 * 
 * 描述

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
如果无解，请返回-1.

数据范围：数组大小满足 
0
≤
n
≤
10000
0≤n≤10000 ， 数组中每个数字都满足 
0
<
v
a
l
≤
10000
0<val≤10000，
0
≤
a
i
m
≤
5000
0≤aim≤5000

要求：时间复杂度 
O
(
n
×
a
i
m
)
O(n×aim) ，空间复杂度 
O
(
a
i
m
)
O(aim)。
 */
public class 兑换零钱1 {
    
    public static void main(String[] args) {
        
        int[] nums = new int[] {1, 2, 5};
        System.out.println(minMoney(nums, 11));

    }

     /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public static int minMoney (int[] arr, int aim) {
        // write code here

        if(0 == aim) return 0;

        if(null==arr || arr.length < 1) return -1;
        if(aim < Arrays.stream(arr).min().getAsInt()) return -1;

        int count = 0;
        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(aim);
        int[] table = new int[aim + 1];
 
        while (!deque.isEmpty()) {
           int len = deque.size();
           for (int i = 0; i < len; i++) {
              int temp = deque.pop();
              if (temp == 0) {
                  return count;
              }
              for (int coin : arr) {
                 if (temp >= coin && table[temp - coin] == 0) {
                     deque.add(temp - coin);
                     table[temp - coin] = 1;
                 }
             }
          }
          count += 1;
     }
     return -1;
    }
}
